package com.example.demo.leetcode.top100;

import java.util.LinkedList;
import java.util.List;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _55全排列
 * @description
 * @date 2023/06/20 17:25
 * <p>
 * ******************************************************
 */
public class _55全排列 {

    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> trace = new LinkedList<>();
        boolean[] used = new boolean[nums.length];

        backtrack1(nums, trace, used);

        return res;

    }

    private void backtrack1(int[] nums, LinkedList<Integer> trace, boolean[] used) {

        if (trace.size() == nums.length) {
            res.add(new LinkedList<>(trace));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            int curr = nums[i];
            trace.add(curr);
            used[i] = true;
            backtrack1(nums, trace, used);
            used[i] = false;
            trace.removeLast();
        }

    }
}
